Overview

Dynamic programming is a strategy to optimize recursion by sacrificing space to improve the solution's runtime complexity.

There is 1D dynamic programming and 2D dynamic programming. In the 1D case, we "remember" results of functions by putting them into a one dimensional list. This technique of "remembering", or caching, function results is called memoization.

There are two ways to approach dynamic programming:

1. Top Down Dynamic Programming involves starting at the end of the problem and working your way back, remembering the solution as you go. You can think of this as an optimized recursive solution.
2. Bottom Up Dynamic Programming involves starting at the beginning of the problem working towards the end. Instead of using recursion, we use a for loop.

We'll be teaching the Top Down approach as it is the easier of the two.

Pattern concept

In order to demonstrate dynamic programming, we'll use the fibonacci sequence.

The fibonacci sequence is a special sequence of numbers in which each number is the sum of the two preceding numbers. The first values in the sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

Step 1 of 32

Use ← → arrow keys

Solution template

There are three main steps to solving a dynamic programming question. If you can figure out all three, you can solve the problem:

• Recursive Helper Function

  Top down dynamic programming always has a memoization component passed down, which is why we need a separate helper function for the recursion.

• Base Case Check

  The base case check defines what the end of our recursion tree should resolve to. This is the most simple case and stops a recursive function.

  In this example question, our base cases are fib(0) = 0 and fib(1) = 1.

  We can also optionally prefill memo in this step.

• Memoization Check

  Check if we've calculated this step before. If we have, return what we saved from our previous computation!

• Recurrence Relation

  If we are at this part of the code, then we're looking at a case that is 1. not the base case, and 2. we haven't computed before.

  For this example question, the recurrence relation is the sum of the previous two numbers.

  Most of the time, this step is a sum of the results of two functions.

  Note

  The recurrence relation is usually the hardest part of the problem. The only way to train yourself to get better at this part is to do more questions and get experience on how these can work. A good exercise is to just look at different dynamic programming questions and see if you can figure out the recurrence relation on your own.

• Memoization List Initialization

  We need to initialize the memoization list in a way such that we can know if we have computed the value or not. The easiest way to do this is by setting the value to None. To create a list of size n, simply multiply a list with None by the size: memo = [None] * n (for fibonacci, we actually use n + 1 because we want the nth number not counting 0).

  Note

  For 2D lists, we want to use the following to initialize your rows * cols list (using list comprehension):

  memo = [[None] * cols for i in range(rows)]

  Do NOT use:

  memo = [[None] * cols] * rows

  As this will duplicate your one list multiple times, leading to unexpected behavior.

How to identify

Does the problem involve any of these?

• Recursion based on previous states (you can break it down into similar subproblems)
  • Fibonnaci Numbers: Find the nth Fibonacci number (by recomputing the sum of its two preceding Fibonacci numbers... by computing the two preceding Fibonnaci numbers before that... and so on).
  • Longest Increasing Subsequence: Find the longest increasing subsequence in a list (by computing whether each element in the subsequence is greater than its previous element's subsequence).
  • Coin Change: Find the minimum number of coins needed to add up to a given amount (by recomputing coins needed for a smaller and smaller amount).
• You are given a choice to go to multiple spots on a one or two dimensional plane
  • Climbing Steps: Find the number of ways to reach the nth step of a set of stairs.
  • Unique Paths: Find the number of unique paths going from top-left corner to the bottom-right corner of a grid if only moving down or right.